package com.leetcode.根据算法进行分类.单调栈相关;

import java.util.ArrayDeque;
import java.util.HashMap;

/**
 * @author: ZhouBert
 * @date: 2021/2/9
 * @description: 496. 下一个更大元素 I
 * https://leetcode-cn.com/problems/next-greater-element-i/
 */
public class A_496_下一个更大元素I {

	public static void main(String[] args) {
		A_496_下一个更大元素I action = new A_496_下一个更大元素I();
		test1(action);
	}

	public static void test1(A_496_下一个更大元素I action) {
		//7
		int[] nums1 = new int[]{4, 1, 2};
		int[] nums2 = new int[]{1, 3, 4, 2};
		int[] res = action.nextGreaterElement(nums1, nums2);
		System.out.println("res = " + res);
	}

	/**
	 * 将 nums2 栈化，
	 *
	 * @param nums1
	 * @param nums2
	 * @return
	 */
	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
		int len1 = nums1.length;
		int len2 = nums2.length;
		//1.先遍历一遍，将 num1 存入 hashMap
		//value - index
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < len1; i++) {
			map.put(nums1[i], i);
		}
		int[] res = new int[len1];
		//初始化为 -1
		for (int i = 0; i < len1; i++) {
			res[i]=-1;
		}
		ArrayDeque<Integer> stack = new ArrayDeque<>();
		for (int i = 0; i < len2; i++) {
			while (!stack.isEmpty() && nums2[i] > stack.peekLast()) {
				//如果当前元素大于栈顶元素，-> 说明栈顶元素已经处理完毕，可以出栈
				Integer value = stack.removeLast();
				Integer index = map.get(value);
				if (index!=null){
					res[index] = nums2[i];
				}

			}
			stack.addLast(nums2[i]);
		}
		return res;
	}
}
